﻿// 标准库或者第三方库
#include <unordered_map>
#include <string>
#include <algorithm>
// 自定义头文件
#include "template_problem01.hxx"
#include "newton.h"
// ACIS
#include "acis/acis.hxx"
#include "acis/api.err"
#include "acis/api.hxx"
#include "acis/body.hxx"
#include "acis/check.hxx"
#include "acis/cstrapi.hxx"
#include "acis/logical.h"
#include "acis/module.hxx"
#include "acis/primtive.hxx"
#include "acis/law_base.hxx"
#include"acis/main_law.hxx"

using namespace std;
// ************************************************************
// 辅助函数声明
struct ItemData {
	bool tag;
	std::string str;
	std::unordered_map<int, double> hashmap;
	ItemData(std::string s = " ", bool t = false) : str(s), tag(t) {}
	friend bool operator==(ItemData m1, ItemData m2) { return m1.str == m2.str && m1.tag == m2.tag; }
};
struct Item {
	double coef;  // 系数
	int expn;     // 指数
	bool operator<(Item b) { return this->expn > b.expn; }
	Item(double c = 0, int e = 0) : coef(c), expn(e) {}
};
/**
 * @brief       ItemData的相乘处理
 * @param[in]   left    左值
 * @param[in]   right   右值
 * @return      ItemData类记录对应次数的系数
 */
ItemData ItemData_times(ItemData left, ItemData right);
/**
 * @brief       获取ItemData的最高次数次数
 * @param[in]   base    给定的ItemData类
 * @return      ItemData类对应最高次数
 */
int Identify_ItemData_string(ItemData base);
/**
 * @brief       计算组合数 C(n, k)
 * @param[in]   n   总体数
 * @param[in]   k   取样数
 * @return      返回值
 */
unsigned long long combination(int n, int k);
/**
 * @brief        计算阶乘 n!
 * @param[in]    n      输入整数 n
 * @return       返回值为 n 的阶乘
 */
unsigned long long factorial(int n);
/**
 * @brief       构建ItemData并返回对应次的方程string
 * @param[in]   x   给定的ItemData类的最高次数
 * @return      给定次数对应的string类
 */
std::string build_tmep(int x);
/**
 * @brief       检查一个双精度浮点数是否为整数
 * @param[in]   value   输入的双精度浮点数
 * @return      如果 value 是整数，则返回 true；否则返回 false
 */
bool isInteger(double value);
/**
 * @brief       获取多项式的最大阶数
 * @param[in]   hashMap     哈希表
 * @return      最大阶数
 */
int find_max_hash_int(std::unordered_map<int, double> hashMap);
/**
 * @brief       提取纯多项式类型对应次数的系数
 * @param[in]   input_law    根结点
 * @return      给定结构数据
 */
ItemData Pure_PostOrder(law* input_law);
/**
 * @brief		获取多项式系数
 * @param[in]	input_law   方程
 * @param[out]	poly		多项式系数与次数
 * @param[out]	tag			是否为多项式方程
 * @return		方程的最大阶数
 */
int get_law_coefficients(law* input_law, std::list<Item>& poly, bool& tag);
/**
 * @brief       对给定方程和区间进行求根
 * @param[in]   poly    多项式系数与次数
 * @param[out]  size    根的数量
 * @param[out]  answer  存储根的数组
 * @param[in]   start   区间左端点
 * @param[in]   end     区间右端点
 */
template <int N> inline void solveEquation(std::list<Item> poly, int* size, double** answer, double start, double end);
// 接口
outcome answer_api_nroots_of_law(law* input_law, double start, double end, int* size, double** answer) {
	API_BEGIN
		if (api_checking_on) {
			check_law(input_law);
		}
	string aa = input_law->string();
	// 获取系数和最大阶数
	std::list<Item> poly;  // 表达方程的一元多项式链表
	// 从law表达方程的树结构中，提取出系数并返回方程最高项次数用于判断几次方程
	bool tag = false;
	int max_degree = get_law_coefficients(input_law, poly, tag);
	switch (max_degree) {
	case 1:
		solveEquation<1>(poly, size, answer, start, end);
		break;
	case 2:
		solveEquation<2>(poly, size, answer, start, end);
		break;
	case 3:
		solveEquation<3>(poly, size, answer, start, end);
		break;
	case 4:
		solveEquation<4>(poly, size, answer, start, end);
		break;
	case 5:
		solveEquation<5>(poly, size, answer, start, end);
		break;
	case 6:
		solveEquation<6>(poly, size, answer, start, end);
		break;
	case 7:
		solveEquation<7>(poly, size, answer, start, end);
		break;
	case 8:
		solveEquation<8>(poly, size, answer, start, end);
		break;
	default:
		break;
	}
	std::sort(*answer, (*answer) + *size);
	API_END
		return result;
}

// 辅助函数实现
std::string build_tmep(int x) {
	// 依据输入最高次数返回字符串。比如x=0返回常数，x=1返回一次函数，依次类推直到8次
	switch (x) {
	case 0:
		return "a";
		break;
	case 1:
		return "ax+b";
		break;
	case 2:
		return "ax^2+bx+c";
		break;
	case 3:
		return "ax^3+bx^2+cx+d";
		break;
	case 4:
		return "ax^4+bx^3+cx^2+dx+e";
		break;
	case 5:
		return "ax^5+bx^4+cx^3+dx^2+ex+f";
		break;
	case 6:
		return "ax^6+bx^5+cx^4+dx^3+ex^2+fx+g";
		break;
	case 7:
		return "ax^7+bx^6+cx^5+dx^4+ex^3+fx^2+gx+h";
		break;
	case 8:
		return "ax^8+bx^7+cx^6+dx^5+ex^4+fx^3+gx^2+hx+i";
		break;
	default:
		return "";
	}
}
int get_law_coefficients(law* input_law, std::list<Item>& poly, bool& tag) {
	// 调用 Pure_PostOrder 函数获取多项式系数
	ItemData res = Pure_PostOrder(input_law);
	tag = res.tag;  // 是否为纯多项式标志
	// 提取到项数链表中
	for (auto i : res.hashmap) {
		poly.push_back(Item(i.second, i.first));
	}
	poly.sort();  // 对链表进行排序
	// 如果链表不为空，则返回最高项系数
	if (!poly.empty())
		return poly.begin()->expn;
	else
		return -1;
}
bool isInteger(double value) {
	// 计算浮点数与其向下取整的差值的绝对值，然后判断是否小于或等于容差
	return fabs(std::floor(value) - value) <= SPAresmch;
}
int find_max_hash_int(std::unordered_map<int, double> hashMap) {
	int maxKey = 0;  // 初始化最大阶数为0
	// 遍历哈希表中的每一个键值对
	for (const auto& pair : hashMap) {
		// 检查值是否为非零
		if (pair.second != 0.0) {
			// 如果当前阶数大于当前最大阶数，则更新最大阶数
			if (pair.first > maxKey) {
				maxKey = pair.first;
			}
		}
	}
	return maxKey;  // 返回具有非零值的最大阶数
}
ItemData Pure_PostOrder(law* input_law) {
	// 碰到单目负号!strcmp(input_law->class_name(), "negate_law")
	if (input_law->isa(NEGATE_LAW_ID)) {
		// 对负号节点的子节点进行递归处理
		ItemData sub = Pure_PostOrder(((negate_law*)input_law)->fsub());
		// 检查子节点是否出错
		if (sub.tag == false && sub.str == "mistake") {
			return ItemData("mistake", false);
		}
		ItemData temp(sub.str, true);
		for (auto& item : sub.hashmap) {
			item.second = -item.second;  // 更新哈希表中的值
			temp.hashmap.insert(item);   // 插入到结果哈希表中
		}
		return temp;
	}
	// 碰到浮点数!strcmp(input_law->class_name(), "constant_law")
	if (input_law->isa(CONSTANT_LAW_ID)) {
		// 获取常量值
		double value = ((constant_law*)input_law)->eval(0);
		ItemData temp("num", true);  // 以字符串'num'创建一个新的ItemData
		temp.hashmap[0] = value;     // 更新哈希表中'num'的数值
		return temp;
	}
	// 碰到变量类! strcmp(input_law->class_name(), "identity_law")
	if (input_law->isa(IDENTITY_LAW_ID)) {
		ItemData temp("x", true);  // 以字符串'x'创建一个新的ItemData
		temp.hashmap[1] = 1;       // 更新哈希表中'x'的数值
		return temp;
	}
	// 后序递归处理左子树和右子树
	ItemData left = Pure_PostOrder(((binary_law*)input_law)->fleft());
	ItemData right = Pure_PostOrder(((binary_law*)input_law)->fright());
	// 检查左子树是否出错
	if (left.tag == false && left.str == "mistake") {
		return ItemData("mistake", false);
	}
	// 检查右子树是否出错
	if (right.tag == false && right.str == "mistake") {
		return ItemData("mistake", false);
	}
	// 根据根结点类型和左右子树返回的数据构成新的数据
	// 遇见幂指类!strcmp(input_law->class_name(), "exponent_law")
	if (input_law->isa(EXPONENT_LAW_ID)) {
		if (right.str != "num")
			// 右侧不是数字或者整数无法识别
			return ItemData("mistake", false);
		else if (left.str == "x") {
			// 左侧为变量x
			ItemData temp("x^n", true);  // 以字符串'x^n'创建一个新的ItemData
			// 指数设为1
			temp.hashmap[right.hashmap[0]] = 1;
			return temp;
		}
		// 左侧为多项式ax+b的形式
		else if ((left.str == "x+num" || left.str == "num+x" || left.str == "ax+b")) {
			// 左侧为一次多项式
			double hValue = right.hashmap[0];      // 指数
			double coefficient = left.hashmap[1];  // x的系数
			double num = left.hashmap[0];          // 常数项
			// 指数为0，即(ax+b)^0=1
			if (fabs(hValue) <= SPAresmch) {
				ItemData temp("num", true);  // 以字符串'num'创建一个新的ItemData
				temp.hashmap[0] = 1;         // 更新哈希表中'num'的数值
				return temp;
			}
			// x的系数为0。b^h的形式
			if (coefficient == 0 && num != 0) {
				ItemData temp("num", true);          // 以字符串'num'创建一个新的ItemData
				temp.hashmap[0] = pow(num, hValue);  // 更新哈希表中'num'的数值为b^h
				return temp;
			}
			// 常数为0。(ax)^h的形式
			else
				// x的系数不为0，且常数为0
				if (coefficient != 0 && num == 0) {
					ItemData temp("x^n", true);  // 以字符串'x^n'创建一个新的ItemData
					// 计算系数a^h
					temp.hashmap[right.hashmap[0]] = pow(coefficient, right.hashmap[0]);
					return temp;
				}
			// x的系数与常数都为0
				else if (coefficient == 0 && num == 0) {
					ItemData temp("num", true);  // 以字符串'num'创建一个新的ItemData
					temp.hashmap[0] = 0;         // 更新哈希表中'num'的数值为0
					return temp;
				}

			// 在2到8次内的（x+num）多项式展开
			if (isInteger(hValue) && 2 <= hValue && hValue <= 8) {
				int hvaluse_int = (int)(hValue);  // 指数取整
				std::string str1 = "";
				ItemData temp(str1, true);
				// 字符串拼接与项数计算
				for (int i = hvaluse_int; i >= 0 && i <= 25; i--) {
					temp.hashmap[i] = pow(coefficient, i) * pow(num, hvaluse_int - i) * combination(hvaluse_int, i);
					if (i != 0 && i != 1)
						str1 = str1 + static_cast<char>(hvaluse_int - i + 'a') + "x^" + std::to_string(i) + "+";
					else if (i == 1)
						str1 = str1 + static_cast<char>(hvaluse_int - i + 'a') + "x" + "+";
					else
						str1 = str1 + static_cast<char>(hvaluse_int - i + 'a');
				}
				temp.str = str1;
				return temp;
			}
			// 阶数大于8无法正常展开
			else {
				ItemData temp("(x+num)^n", true);
				temp.hashmap[right.hashmap[0]] = 1;
				return temp;
			}
		}
		// 左侧为多项式，大于1次小于等于8次
		else if (Identify_ItemData_string(left) <= 8) {
			double v = right.hashmap[0];  // 右子树系数
			// 如果右子树系数为0
			if (v == 0) {
				// 以字符串 'num'创建一个新的ItemData
				ItemData temp("num", true);
				temp.hashmap[0] = 1;  // 更新哈希表中'num'的数值为1
				return temp;
			}
			// 如果右子树系数为1，直接返回左子树
			else if (v == 1)
				return left;
			// 右子树系数为整数且在2-6之间
			else if (isInteger(v) && 2 <= v && v <= 6) {
				ItemData temp = left;
				// 将左右子树对应相乘
				for (int i = 1; i < v; i++) {
					temp = ItemData_times(left, temp);
				}
				return temp;
			}
			else
				return ItemData("mistake", false);
		}
		// 左右子树均为数字的情况
		else if (left.str == "num") {
			// 左子树的常数值不为0，a^b的情况。计算值，并构建返回
			if (left.hashmap[0] != 0) {
				ItemData temp("num", true);
				temp.hashmap[0] = pow(left.hashmap[0], right.hashmap[0]);
				return temp;
			}
			// 左子树的常数值为0，0^b的情况。值设为1，并构建返回
			else if (left.hashmap[0] == 0 && right.hashmap[0] != 0) {
				ItemData temp("num", true);
				temp.hashmap[0] = 1;
				return temp;
			}
			// 否则，返回错误信息
			else
				return ItemData("mistake", false);
		}
		return ItemData("mistake", false);
	}
	// 碰到乘法! strcmp(input_law->class_name(), "times_law")
	else if (input_law->isa(TIMES_LAW_ID)) {
		// 左右子树均无错误
		if (left.tag && right.tag) {
			// 左边是一个数字
			if (left.str == "num") {
				// 以右子树字符串创建一个新的ItemData
				ItemData temp(right.str, true);
				double val = left.hashmap[0];
				for (auto& item : right.hashmap) {
					item.second *= val;         // 更新右子树哈希表中的值
					temp.hashmap.insert(item);  // 插入到结果哈希表中
				}
				return temp;
			}
			// 右边是一个数字
			else if (right.str == "num") {
				// 以左子树字符创建一个新的ItemData
				ItemData temp(left.str, true);
				double val = right.hashmap[0];
				for (auto& item : left.hashmap) {
					item.second *= val;         // 更新左子树哈希表中的值
					temp.hashmap.insert(item);  // 插入到结果哈希表中
				}
				return temp;
			}
			// 否则进行多项式相乘
			else {
				return ItemData_times(left, right);
			}
		}
	}
	// 碰到除法! strcmp(input_law->class_name(), "division_law")
	else if (input_law->isa(DIVISION_LAW_ID)) {
		// 左右子树均无错误
		if (left.tag && right.tag) {
			// 左边是一个数字
			if (left.str == "num") {
				// 以右子树字符串创建一个新的ItemData
				ItemData temp(right.str, true);
				double val = left.hashmap[0];
				for (auto& item : right.hashmap) {
					item.second /= val;         // 更新右子树哈希表中的值
					temp.hashmap.insert(item);  // 插入到结果哈希表中
				}
				return temp;
			}
			// 右边是一个数字
			else if (right.str == "num") {
				// 以左右子树字符创建一个新的ItemData
				ItemData temp(left.str, true);
				double val = right.hashmap[0];
				for (auto& item : left.hashmap) {
					item.second /= val;         // 更新左子树哈希表中的值
					temp.hashmap.insert(item);  // 插入到结果哈希表中
				}
				return temp;
			}
		}
	}
	// 碰到减法 ! strcmp(input_law->class_name(), "minus_law")
	else if (input_law->isa(MINUS_LAW_ID)) {
		// 左右子树都是数值
		if (left.str == "num" && right.str == "num") {
			// 以字符串'num'创建一个新的ItemData
			ItemData temp("num", true);
			temp.hashmap[0] = left.hashmap[0] - right.hashmap[0];  // 更新哈希表中的数值
			return temp;
		}
		// 左右字数拼接创建一个新的ItemData
		ItemData temp(left.str + "+" + right.str, true);
		// 获取左子树哈希表中的最大阶数
		int left_max_t = find_max_hash_int(left.hashmap);
		// 获取右子树哈希表中的最大阶数
		int right_max_t = find_max_hash_int(right.hashmap);
		// 获取左右子树哈希表中的最大阶数
		int max_t = std::max(left_max_t, right_max_t);
		std::string str1 = "";
		// 如果最大阶数大于等于8
		if (max_t >= 8) {
			temp.hashmap = left.hashmap;  // 复制左子树的哈希表
			for (auto item : right.hashmap) {
				auto it = temp.hashmap.find(item.first);
				// 如果右子树的哈希表项在左子树哈希表中存在，则减去该值
				if (it != temp.hashmap.end()) {
					temp.hashmap[it->first] -= item.second;
				}
				// 否则，插入该值的负值
				else {
					temp.hashmap[item.first] = -item.second;
				}
			}
			return temp;
		}
		temp.hashmap = left.hashmap;  // 复制左子树的哈希表
		for (auto item : right.hashmap) {
			auto it = temp.hashmap.find(item.first);
			// 如果右子树的哈希表项在左子树哈希表中存在，则减去该值
			if (it != temp.hashmap.end()) {
				temp.hashmap[it->first] -= item.second;
			}
			// 否则，插入该值的负值
			else {
				temp.hashmap[item.first] = -item.second;
			}
		}
		// 构建多项式
		temp.str = build_tmep(find_max_hash_int(temp.hashmap));
		return temp;
	}
	// 遇到加法! strcmp(input_law->class_name(), "plus_law")
	else if (input_law->isa(PLUS_LAW_ID)) {
		// 左右子树都是数值
		if (left.str == "num" && right.str == "num") {
			// 以字符串'num'创建一个新的ItemData
			ItemData temp("num", true);
			temp.hashmap[0] = left.hashmap[0] + right.hashmap[0];  // 更新哈希表中的数值
			return temp;
		}
		// 如果左子树为空返回右子树
		if (left.str == "") return right;
		// 如果右子树为空返回左子树
		if (right.str == "") return left;
		// 左右字数拼接创建一个新的ItemData
		ItemData temp(left.str + "+" + right.str, true);
		// 获取左子树哈希表中的最大阶数
		int left_max_t = find_max_hash_int(left.hashmap);
		// 获取右子树哈希表中的最大阶数
		int right_max_t = find_max_hash_int(right.hashmap);
		// 获取左右子树哈希表中的最大阶数
		int max_t = std::max(left_max_t, right_max_t);
		std::string str1 = "";
		// 如果最大阶数大于等于8
		if (max_t >= 8) {
			temp.hashmap = left.hashmap;  // 复制左子树的哈希表
			for (auto item : right.hashmap) {
				auto it = temp.hashmap.find(item.first);
				// 如果右子树的哈希表项在左子树哈希表中存在，则加上该值
				if (it != temp.hashmap.end()) {
					temp.hashmap[it->first] += item.second;
				}
				// 否则，直接插入该值
				else {
					temp.hashmap[item.first] = item.second;
				}
			}
			return temp;
		}
		temp.hashmap = left.hashmap;  // 复制左子树的哈希表
		for (auto item : right.hashmap) {
			auto it = temp.hashmap.find(item.first);
			// 如果右子树的哈希表项在左子树哈希表中存在，则加上该值
			if (it != temp.hashmap.end()) {
				temp.hashmap[it->first] += item.second;
			}
			// 否则，直接插入该值
			else {
				temp.hashmap[item.first] = item.second;
			}
		}
		// 构建多项式
		temp.str = build_tmep(find_max_hash_int(temp.hashmap));
		return temp;
	}
	// 否则，返回错误信息
	else {
		return ItemData("mistake", false);
	}
	return ItemData("mistake", false);  // 返回默认错误信息
}
template <int N> inline void solveEquation(std::list<Item> poly, int* size, double** answer, double start, double end) {
	// 将方程系数提取到系数数组中
	double coeffs[N + 1] = { 0 };
	std::list<Item>::iterator p1;
	// 遍历多项式链表
	for (p1 = poly.begin(); p1 != poly.end(); p1++) {
		coeffs[p1->expn] = p1->coef;  // 将每个项的系数提取到系数数组中
	}
	// 删除定义域外的根
	double root[N] = { 0 };
	// 求解多项式方程的根
	int root_number = cy::PolynomialRoots<N, double>(root, coeffs, SPAresnor);
	answer[0] = ACIS_NEW double[N];
	int index = 0;
	// 遍历根数组
	for (int i = 0; i < root_number && index < N; i++) {
		// 判断根是否在定义域内
		if (root[i] >= start - SPAresabs && root[i] <= end + SPAresabs) {
			answer[0][index++] = root[i];
		}
	}
	*size = index;  // 更新根的数量
}
unsigned long long combination(int n, int k) {
	return factorial(n) / (factorial(k) * factorial(n - k));
}
unsigned long long factorial(int n) {
	// 如果 n 是 0 或 1，则返回 1，因为 0! 和 1! 都是 1
	if (n == 0 || n == 1) {
		return 1;
	}
	// 递归调用 factorial 函数，计算 n * (n-1)!
	else {
		return n * factorial(n - 1);
	}
}
int Identify_ItemData_string(ItemData base) {
	// 如果ItemData结构的字符串表示为"x^n"返回x的最高次数
	if (base.str == "x^n") return find_max_hash_int(base.hashmap);
	// 依据ItemData结构的字符串对应哈希表获取，多项式最高次数
	switch (find_max_hash_int(base.hashmap)) {
	case 0:
		return 0;
		break;
	case 1:
		if (base.str == "x" || base.str == "ax") return 1;
		if (base.str == "ax+b" || base.str == "x+num" || base.str == "num+x" || base.str == "x+b") return 1;
		break;
	case 2:
		if (base.str == "ax^2+bx+c") return 2;
		break;
	case 3:
		if (base.str == "ax^3+bx^2+cx+d") return 3;
		break;
	case 4:
		if (base.str == "ax^4+bx^3+cx^2+dx+e") return 4;
		break;
	case 5:
		if (base.str == "ax^5+bx^4+cx^3+dx^2+ex+f") return 5;
		break;
	case 6:
		if (base.str == "ax^6+bx^5+cx^4+dx^3+ex^2+fx+g") return 6;
		break;
	case 7:
		if (base.str == "ax^7+bx^6+cx^5+dx^4+ex^3+fx^2+gx+h") return 7;
		break;
	case 8:
		if (base.str == "ax^8+bx^7+cx^6+dx^5+ex^4+fx^3+gx^2+hx+i") return 8;
		break;
	default:
		return 9;
	}
	return 9;
}
ItemData ItemData_times(ItemData left, ItemData right) {
	// ItemData的相乘处理
	int l, r;
	l = Identify_ItemData_string(left);   // 获取左值最高次数
	r = Identify_ItemData_string(right);  // 获取右值的最高次数
	// 如果左值或右值的最高次数超出了8，返回错误信息
	if (l >= 9 || r >= 9) {
		ItemData temp("mistake", true);
		return temp;
	}
	// 否则，根据次数创建一个临时的 ItemData
	else {
		ItemData temp(build_tmep(l + r), true);
		// 对左值和右值的系数进行相乘，并将结果存储在临时对象的 hashmap 中
		for (int i = 0; i <= l; i++) {
			for (int j = 0; j <= r; j++) {
				temp.hashmap[j + i] += left.hashmap[i] * right.hashmap[j];
			}
		}
		return temp;
	}
}